#include "../stdafx.h"
#include "../include/Platform.h"

#include "../util/util.h"
#include "Partitioning.h"
#include "RunStyles.h"
#include "ContractionState.h"
#include "CellBuffer.h"
#include "KeyMap.h"
#include "Indicator.h"
#include "XPM.h"
#include "LineMarker.h"
#include "Style.h"
#include "ViewStyle.h"
#include "CharClassify.h"
#include "Decoration.h"
#include "Document.h"
#include "Selection.h"
#include "PositionCache.h"

namespace soy{

	static inline bool IsControlCharacter(int ch) {
		// iscntrl returns true for lots of chars > 127 which are displayable
		return ch >= 0 && ch < ' ';
	}

	LineLayout::LineLayout(int maxLineLength_) :
	lineStarts(0),
		lenLineStarts(0),
		lineNumber(-1),
		inCache(false),
		maxLineLength(-1),
		numCharsInLine(0),
		numCharsBeforeEOL(0),
		validity(llInvalid),
		xHighlightGuide(0),
		highlightColumn(0),
		psel(NULL),
		containsCaret(false),
		edgeColumn(0),
		chars(0),
		styles(0),
		styleBitsSet(0),
		indicators(0),
		positions(0),
		hsStart(0),
		hsEnd(0),
		widthLine(wrapWidthInfinite),
		lines(1),
		wrapIndent(0) {
			bracePreviousStyles[0] = 0;
			bracePreviousStyles[1] = 0;
			Resize(maxLineLength_);
	}

	LineLayout::~LineLayout() {
		Free();
	}

	void LineLayout::Resize(int maxLineLength_) {
		if (maxLineLength_ > maxLineLength) {
			Free();
			chars = new char[maxLineLength_ + 1];
			styles = new unsigned char[maxLineLength_ + 1];
			indicators = new char[maxLineLength_ + 1];
			// Extra position allocated as sometimes the Windows
			// GetTextExtentExPoint API writes an extra element.
			positions = new int[maxLineLength_ + 1 + 1];
			maxLineLength = maxLineLength_;
		}
	}

	void LineLayout::Free() {
		delete []chars;
		chars = 0;
		delete []styles;
		styles = 0;
		delete []indicators;
		indicators = 0;
		delete []positions;
		positions = 0;
		delete []lineStarts;
		lineStarts = 0;
	}

	void LineLayout::Invalidate(validLevel validity_) {
		if (validity > validity_)
			validity = validity_;
	}

	int LineLayout::LineStart(int line) const {
		if (line <= 0) {
			return 0;
		} else if ((line >= lines) || !lineStarts) {
			return numCharsInLine;
		} else {
			return lineStarts[line];
		}
	}

	int LineLayout::LineLastVisible(int line) const {
		if (line < 0) {
			return 0;
		} else if ((line >= lines-1) || !lineStarts) {
			return numCharsBeforeEOL;
		} else {
			return lineStarts[line+1];
		}
	}

	bool LineLayout::InLine(int offset, int line) const {
		return ((offset >= LineStart(line)) && (offset < LineStart(line + 1))) ||
			((offset == numCharsInLine) && (line == (lines-1)));
	}

	void LineLayout::SetLineStart(int line, int start) {
		if ((line >= lenLineStarts) && (line != 0)) {
			int newMaxLines = line + 20;
			int *newLineStarts = new int[newMaxLines];
			for (int i = 0; i < newMaxLines; i++) {
				if (i < lenLineStarts)
					newLineStarts[i] = lineStarts[i];
				else
					newLineStarts[i] = 0;
			}
			delete []lineStarts;
			lineStarts = newLineStarts;
			lenLineStarts = newMaxLines;
		}
		lineStarts[line] = start;
	}

	void LineLayout::SetBracesHighlight(Range rangeLine, Position braces[],
		char bracesMatchStyle, int xHighlight, bool ignoreStyle) {
			if (!ignoreStyle && rangeLine.ContainsCharacter(braces[0])) {
				int braceOffset = braces[0] - rangeLine.start;
				if (braceOffset < numCharsInLine) {
					bracePreviousStyles[0] = styles[braceOffset];
					styles[braceOffset] = bracesMatchStyle;
				}
			}
			if (!ignoreStyle && rangeLine.ContainsCharacter(braces[1])) {
				int braceOffset = braces[1] - rangeLine.start;
				if (braceOffset < numCharsInLine) {
					bracePreviousStyles[1] = styles[braceOffset];
					styles[braceOffset] = bracesMatchStyle;
				}
			}
			if ((braces[0] >= rangeLine.start && braces[1] <= rangeLine.end) ||
				(braces[1] >= rangeLine.start && braces[0] <= rangeLine.end)) {
					xHighlightGuide = xHighlight;
			}
	}

	void LineLayout::RestoreBracesHighlight(Range rangeLine, Position braces[], bool ignoreStyle) {
		if (!ignoreStyle && rangeLine.ContainsCharacter(braces[0])) {
			int braceOffset = braces[0] - rangeLine.start;
			if (braceOffset < numCharsInLine) {
				styles[braceOffset] = bracePreviousStyles[0];
			}
		}
		if (!ignoreStyle && rangeLine.ContainsCharacter(braces[1])) {
			int braceOffset = braces[1] - rangeLine.start;
			if (braceOffset < numCharsInLine) {
				styles[braceOffset] = bracePreviousStyles[1];
			}
		}
		xHighlightGuide = 0;
	}

	int LineLayout::FindBefore(int x, int lower, int upper) const {
		do {
			int middle = (upper + lower + 1) / 2; 	// Round high
			int posMiddle = positions[middle];
			if (x < posMiddle) {
				upper = middle - 1;
			} else {
				lower = middle;
			}
		} while (lower < upper);
		return lower;
	}

	int LineLayout::EndLineStyle() const {
		return styles[numCharsBeforeEOL > 0 ? numCharsBeforeEOL-1 : 0];
	}

	LineLayoutCache::LineLayoutCache() :
	level(0), length(0), size(0), cache(0),
		allInvalidated(false), styleClock(-1), useCount(0) {
			Allocate(0);
	}

	LineLayoutCache::~LineLayoutCache() {
		Deallocate();
	}

	void LineLayoutCache::Allocate(int length_) {
		assert(cache == NULL);
		allInvalidated = false;
		length = length_;
		size = length;
		if (size > 1) {
			size = (size / 16 + 1) * 16;
		}
		if (size > 0) {
			cache = new LineLayout * [size];
		}
		for (int i = 0; i < size; i++)
			cache[i] = 0;
	}

	void LineLayoutCache::AllocateForLevel(int linesOnScreen, int linesInDoc) {
		assert(useCount == 0);
		int lengthForLevel = 0;
		if (level == llcCaret) {
			lengthForLevel = 1;
		} else if (level == llcPage) {
			lengthForLevel = linesOnScreen + 1;
		} else if (level == llcDocument) {
			lengthForLevel = linesInDoc;
		}
		if (lengthForLevel > size) {
			Deallocate();
			Allocate(lengthForLevel);
		} else {
			if (lengthForLevel < length) {
				for (int i = lengthForLevel; i < length; i++) {
					delete cache[i];
					cache[i] = 0;
				}
			}
			length = lengthForLevel;
		}
		assert(length == lengthForLevel);
		assert(cache != NULL || length == 0);
	}

	void LineLayoutCache::Deallocate() {
		assert(useCount == 0);
		for (int i = 0; i < length; i++)
			delete cache[i];
		delete []cache;
		cache = 0;
		length = 0;
		size = 0;
	}

	void LineLayoutCache::Invalidate(LineLayout::validLevel validity_) {
		if (cache && !allInvalidated) {
			for (int i = 0; i < length; i++) {
				if (cache[i]) {
					cache[i]->Invalidate(validity_);
				}
			}
			if (validity_ == LineLayout::llInvalid) {
				allInvalidated = true;
			}
		}
	}

	void LineLayoutCache::SetLevel(int level_) {
		allInvalidated = false;
		if ((level_ != -1) && (level != level_)) {
			level = level_;
			Deallocate();
		}
	}

	LineLayout *LineLayoutCache::Retrieve(int lineNumber, int lineCaret, int maxChars, int styleClock_,
		int linesOnScreen, int linesInDoc) {
			AllocateForLevel(linesOnScreen, linesInDoc);
			if (styleClock != styleClock_) {
				Invalidate(LineLayout::llCheckTextAndStyle);
				styleClock = styleClock_;
			}
			allInvalidated = false;
			int pos = -1;
			LineLayout *ret = 0;
			if (level == llcCaret) {
				pos = 0;
			} else if (level == llcPage) {
				if (lineNumber == lineCaret) {
					pos = 0;
				} else if (length > 1) {
					pos = 1 + (lineNumber % (length - 1));
				}
			} else if (level == llcDocument) {
				pos = lineNumber;
			}
			if (pos >= 0) {
				assert(useCount == 0);
				if (cache && (pos < length)) {
					if (cache[pos]) {
						if ((cache[pos]->lineNumber != lineNumber) ||
							(cache[pos]->maxLineLength < maxChars)) {
								delete cache[pos];
								cache[pos] = 0;
						}
					}
					if (!cache[pos]) {
						cache[pos] = new LineLayout(maxChars);
					}
					if (cache[pos]) {
						cache[pos]->lineNumber = lineNumber;
						cache[pos]->inCache = true;
						ret = cache[pos];
						useCount++;
					}
				}
			}

			if (!ret) {
				ret = new LineLayout(maxChars);
				ret->lineNumber = lineNumber;
			}

			return ret;
	}

	void LineLayoutCache::Dispose(LineLayout *ll) {
		allInvalidated = false;
		if (ll) {
			if (!ll->inCache) {
				delete ll;
			} else {
				useCount--;
			}
		}
	}

	void BreakFinder::Insert(int val) {
		// Expand if needed
		if (saeLen >= saeSize) {
			saeSize *= 2;
			int *selAndEdgeNew = new int[saeSize];
			for (unsigned int j = 0; j<saeLen; j++) {
				selAndEdgeNew[j] = selAndEdge[j];
			}
			delete []selAndEdge;
			selAndEdge = selAndEdgeNew;
		}

		if (val >= nextBreak) {
			for (unsigned int j = 0; j<saeLen; j++) {
				if (val == selAndEdge[j]) {
					return;
				}
				if (val < selAndEdge[j]) {
					for (unsigned int k = saeLen; k>j; k--) {
						selAndEdge[k] = selAndEdge[k-1];
					}
					saeLen++;
					selAndEdge[j] = val;
					return;
				}
			}
			// Not less than any so append
			selAndEdge[saeLen++] = val;
		}
	}

	extern bool BadUTF(const char *s, int len, int &trailBytes);

	static int NextBadU(const char *s, int p, int len, int &trailBytes) {
		while (p < len) {
			p++;
			if (BadUTF(s + p, len - p, trailBytes))
				return p;
		}
		return -1;
	}

	BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posLineStart_,
		int xStart, bool breakForSelection, Document *pdoc_) :
	ll(ll_),
		lineStart(lineStart_),
		lineEnd(lineEnd_),
		posLineStart(posLineStart_),
		nextBreak(lineStart_),
		saeSize(0),
		saeLen(0),
		saeCurrentPos(0),
		saeNext(0),
		subBreak(-1),
		pdoc(pdoc_) {
			saeSize = 8;
			selAndEdge = new int[saeSize];
			for (unsigned int j=0; j < saeSize; j++) {
				selAndEdge[j] = 0;
			}

			// Search for first visible break
			// First find the first visible character
			nextBreak = ll->FindBefore(xStart, lineStart, lineEnd);
			// Now back to a style break
			while ((nextBreak > lineStart) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) {
				nextBreak--;
			}

			if (breakForSelection) {
				SelectionPosition posStart(posLineStart);
				SelectionPosition posEnd(posLineStart + lineEnd);
				SelectionSegment segmentLine(posStart, posEnd);
				for (size_t r=0; r<ll->psel->Count(); r++) {
					SelectionSegment portion = ll->psel->Range(r).Intersect(segmentLine);
					if (!(portion.start == portion.end)) {
						if (portion.start.IsValid())
							Insert(portion.start.Position() - posLineStart - 1);
						if (portion.end.IsValid())
							Insert(portion.end.Position() - posLineStart - 1);
					}
				}
			}

			Insert(ll->edgeColumn - 1);
			Insert(lineEnd - 1);

			if (pdoc && (SC_CP_UTF8 == pdoc->dbcsCodePage)) {
				int trailBytes=0;
				for (int pos = -1;;) {
					pos = NextBadU(ll->chars, pos, lineEnd, trailBytes);
					if (pos < 0)
						break;
					Insert(pos-1);
					Insert(pos);
				}
			}
			saeNext = (saeLen > 0) ? selAndEdge[0] : -1;
	}

	BreakFinder::~BreakFinder() {
		delete []selAndEdge;
	}

	int BreakFinder::First() const {
		return nextBreak;
	}

	int BreakFinder::Next() {
		if (subBreak == -1) {
			int prev = nextBreak;
			while (nextBreak < lineEnd) {
				if ((ll->styles[nextBreak] != ll->styles[nextBreak + 1]) ||
					(nextBreak == saeNext) ||
					IsControlCharacter(ll->chars[nextBreak]) || IsControlCharacter(ll->chars[nextBreak + 1])) {
						if (nextBreak == saeNext) {
							saeCurrentPos++;
							saeNext = (saeLen > saeCurrentPos) ? selAndEdge[saeCurrentPos] : -1;
						}
						nextBreak++;
						if ((nextBreak - prev) < lengthStartSubdivision) {
							return nextBreak;
						}
						break;
				}
				nextBreak++;
			}
			if ((nextBreak - prev) < lengthStartSubdivision) {
				return nextBreak;
			}
			subBreak = prev;
		}
		// Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
		// For very long runs add extra breaks after spaces or if no spaces before low punctuation.
		if ((nextBreak - subBreak) <= lengthEachSubdivision) {
			subBreak = -1;
			return nextBreak;
		} else {
			subBreak += pdoc->SafeSegment(ll->chars + subBreak, nextBreak-subBreak, lengthEachSubdivision);
			if (subBreak >= nextBreak) {
				subBreak = -1;
				return nextBreak;
			} else {
				return subBreak;
			}
		}
	}

	PositionCacheEntry::PositionCacheEntry() :
	styleNumber(0), len(0), clock(0), positions(0) {
	}

	void PositionCacheEntry::Set(unsigned int styleNumber_, const char *s_,
		unsigned int len_, int *positions_, unsigned int clock_) {
			Clear();
			styleNumber = styleNumber_;
			len = len_;
			clock = clock_;
			if (s_ && positions_) {
				positions = new short[len + (len + 1) / 2];
				for (unsigned int i=0; i<len; i++) {
					positions[i] = static_cast<short>(positions_[i]);
				}
				memcpy(reinterpret_cast<char *>(positions + len), s_, len);
			}
	}

	PositionCacheEntry::~PositionCacheEntry() {
		Clear();
	}

	void PositionCacheEntry::Clear() {
		delete []positions;
		positions = 0;
		styleNumber = 0;
		len = 0;
		clock = 0;
	}

	bool PositionCacheEntry::Retrieve(unsigned int styleNumber_, const char *s_,
		unsigned int len_, int *positions_) const {
			if ((styleNumber == styleNumber_) && (len == len_) &&
				(memcmp(reinterpret_cast<char *>(positions + len), s_, len)== 0)) {
					for (unsigned int i=0; i<len; i++) {
						positions_[i] = positions[i];
					}
					return true;
			} else {
				return false;
			}
	}

	int PositionCacheEntry::Hash(unsigned int styleNumber, const char *s, unsigned int len) {
		unsigned int ret = s[0] << 7;
		for (unsigned int i=0; i<len; i++) {
			ret *= 1000003;
			ret ^= s[i];
		}
		ret *= 1000003;
		ret ^= len;
		ret *= 1000003;
		ret ^= styleNumber;
		return ret;
	}

	bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) const {
		return clock > other.clock;
	}

	void PositionCacheEntry::ResetClock() {
		if (clock > 0) {
			clock = 1;
		}
	}

	PositionCache::PositionCache() {
		size = 0x400;
		clock = 1;
		pces = new PositionCacheEntry[size];
		allClear = true;
	}

	PositionCache::~PositionCache() {
		Clear();
		delete []pces;
	}

	void PositionCache::Clear() {
		if (!allClear) {
			for (size_t i=0; i<size; i++) {
				pces[i].Clear();
			}
		}
		clock = 1;
		allClear = true;
	}

	void PositionCache::SetSize(size_t size_) {
		Clear();
		delete []pces;
		size = size_;
		pces = new PositionCacheEntry[size];
	}

	void PositionCache::MeasureWidths(Surface *surface, ViewStyle &vstyle, unsigned int styleNumber,
		const char *s, unsigned int len, int *positions, Document *pdoc) {

			allClear = false;
			int probe = -1;
			if ((size > 0) && (len < 30)) {
				// Only store short strings in the cache so it doesn't churn with
				// long comments with only a single comment.

				// Two way associative: try two probe positions.
				int hashValue = PositionCacheEntry::Hash(styleNumber, s, len);
				probe = hashValue % size;
				if (pces[probe].Retrieve(styleNumber, s, len, positions)) {
					return;
				}
				int probe2 = (hashValue * 37) % size;
				if (pces[probe2].Retrieve(styleNumber, s, len, positions)) {
					return;
				}
				// Not found. Choose the oldest of the two slots to replace
				if (pces[probe].NewerThan(pces[probe2])) {
					probe = probe2;
				}
			}
			if (len > BreakFinder::lengthStartSubdivision) {
				// Break up into segments
				unsigned int startSegment = 0;
				int xStartSegment = 0;
				while (startSegment < len) {
					unsigned int lenSegment = pdoc->SafeSegment(s + startSegment, len - startSegment, BreakFinder::lengthEachSubdivision);
					surface->MeasureWidths(vstyle.styles[styleNumber].font, s + startSegment, lenSegment, positions + startSegment);
					for (unsigned int inSeg = 0; inSeg < lenSegment; inSeg++) {
						positions[startSegment + inSeg] += xStartSegment;
					}
					xStartSegment = positions[startSegment + lenSegment - 1];
					startSegment += lenSegment;
				}
			} else {
				surface->MeasureWidths(vstyle.styles[styleNumber].font, s, len, positions);
			}
			if (probe >= 0) {
				clock++;
				if (clock > 60000) {
					// Since there are only 16 bits for the clock, wrap it round and
					// reset all cache entries so none get stuck with a high clock.
					for (size_t i=0; i<size; i++) {
						pces[i].ResetClock();
					}
					clock = 2;
				}
				pces[probe].Set(styleNumber, s, len, positions, clock);
			}
	}

};
